#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;
#define maxn 10001
const int INF = 2147483647;

int n,V,S;
int dis[maxn];
struct edge {
	int to, weight;
};
edge make_edge(int to, int weight){
	edge temp;
	temp.to=to;
	temp.weight=weight;
	return temp;
}
vector<edge> G[maxn];
struct node {
	int id, dis;
	bool operator> (const node a) const {
		return this->dis > a.dis;
	}
};
node make_node(int id, int dis){
	node temp;
	temp.id=id;
	temp.dis=dis;
	return temp;
}
priority_queue<node, vector<node>, greater<node> > pque;

void dijkstra(int s){
	fill(dis,dis+n+1,INF);
	dis[s]=0;
	pque.push(make_node(s, 0));

	while(!pque.empty()){
		node p = pque.top();
		pque.pop();
		int v = p.id;
		if(dis[v] < p.dis) continue;
		for(int i=0; i<G[v].size(); i++){
			edge e = G[v][i];
			if(dis[e.to] > dis[v]+e.weight){
				dis[e.to] = dis[v]+e.weight;
				pque.push(make_node(e.to, dis[e.to]));
			}
		}
	}
}

int main(){
	cin>>n>>V>>S;
	for(int i=0; i<V; i++){
		int u,v,w;
		cin>>u>>v>>w;
		G[u].push_back(make_edge(v,w));
	}

	dijkstra(S);
	for(int v=1; v<=n; v++){
		cout<<dis[v]<<" ";
	}
	
	return 0;
}